#include<vector>
#include<string>
using namespace std;
class Solution {
public:
    //01背包
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<vector<int>>>dp(strs.size()+1,vector<vector<int>>(m+1,vector<int>(n+1)));
        for(int i=1;i<=strs.size();i++){
            int z=0,o=0;
            for(char ch:strs[i-1])
                if(ch=='0') ++z;
                else ++o;
            for(int j=0;j<=m;j++){
                for(int k=0;k<=n;k++){
                    dp[i][j][k]=dp[i-1][j][k];
                    if((j-z>=0&&k-o>=0)&&dp[i-1][j-z][k-o]+1>dp[i][j][k])
                    dp[i][j][k]=dp[i-1][j-z][k-o]+1;
                }
            }
        }
        return dp.back()[m][n];
    }
};
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<vector<int>>>dp(strs.size()+1,vector<vector<int>>(m+1,vector<int>(n+1,-1)));
        int ans=0;
        dp[0][0][0]=0;
        for(int i=1;i<=strs.size();i++){
            int z=0,o=0;
            for(char ch:strs[i-1])
                if(ch=='0') ++z;
                else ++o;
            for(int j=0;j<=m;j++){
                for(int k=0;k<=n;k++){
                    dp[i][j][k]=dp[i-1][j][k];
                    if((j-z>=0&&k-o>=0)&&dp[i-1][j-z][k-o]!=-1&&dp[i-1][j-z][k-o]+1>dp[i][j][k])
                    dp[i][j][k]=dp[i-1][j-z][k-o]+1;
                    ans=max(ans,dp[i][j][k]);
                }
            }
        }
        return ans;
    }
};
//空间优化
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        dp[0][0]=0;
        for(int i=1;i<=strs.size();i++){
            int z=0,o=0;
            for(char ch:strs[i-1])
                if(ch=='0') ++z;    else ++o;
            for(int j=m;j>=0;j--){
                for(int k=n;k>=0;k--){
                    if((j>=z&&k>=o)&&dp[j-z][k-o]+1>dp[j][k])
                        dp[j][k]=dp[j-z][k-o]+1;
                }
            }
        }
        return dp[m][n];
    }
};